package simulator.services.searchAlgoritms;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import simulator.graphData.Graph;

/**
 * This algorithm find the shortest path between two vertices in the graph.
 *
 * @author Roee
 */
public class Dijkstra extends PathGenerator {

    private final List<String> nodes;
    private Set<String> settledNodes;
    private Set<String> unSettledNodes;
    private Map<String, String> predecessors;
    private Map<String, Double> distance;

    public Dijkstra(Graph g) {
        super(g);
        this.nodes = new ArrayList<>();
        for (String vertex : graph.getConnectedVertexSet()) {
            nodes.add(vertex);
        }
    }

    /*  this code will be modified and extended later, first i want to
     support basic functionality */
    @Override
    public ArrayDeque<String> generate(String src, String target) {
        return generatePath(src, target);
    }

    public ArrayDeque<String> generatePath(String start, String goal) {
        execute(start);
        ArrayDeque<String> path = getPath(goal);
        return path;

    }

    public void execute(String source) {
        settledNodes = new HashSet<>();
        unSettledNodes = new HashSet<>();
        distance = new HashMap<>();
        predecessors = new HashMap<>();
        distance.put(source, 0.0);
        unSettledNodes.add(source);
        while (unSettledNodes.size() > 0) {
            String node = getMinimum(unSettledNodes);
            settledNodes.add(node);
            unSettledNodes.remove(node);
            findMinimalDistances(node);
        }
    }

    private void findMinimalDistances(String node) {
        List<String> adjacentNodes = getNeighbors(node);
        for (String target : adjacentNodes) {
            if (getShortestDistance(target) > getShortestDistance(node) + getDistance(node, target)) {
                distance.put(target, getShortestDistance(node) + getDistance(node, target));
                predecessors.put(target, node);
                unSettledNodes.add(target);
            }
        }
    }

    private double getDistance(String node, String target) {
        return this.graph.calcEdgeLength(node, target);
    }

    private List<String> getNeighbors(String node) {
        List<String> neighbors = new ArrayList<>();

        for (String v : this.graph.getAdjacentsOf(node)) {
            if (!isSettled(v)) {
                neighbors.add(v);
            }
        }
        return neighbors;
    }

    private String getMinimum(Set<String> vertexes) {
        String minimum = null;
        for (String vertex : vertexes) {
            if (minimum == null) {
                minimum = vertex;
            } else {
                if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
                    minimum = vertex;
                }
            }
        }
        return minimum;
    }

    private boolean isSettled(String vertex) {
        return settledNodes.contains(vertex);
    }

    private Double getShortestDistance(String destination) {
        Double d = distance.get(destination);
        if (d == null) {
            return Double.MAX_VALUE;
        } else {
            return d;
        }
    }

    /*
     * This method returns the path from the source to the selected target and
     * NULL if no path exists
     */
    public ArrayDeque<String> getPath(String target) {
        ArrayDeque<String> path = new ArrayDeque<>();
        String step = target;
        // check if a path exists
        if (predecessors.get(step) == null) {
            return new ArrayDeque<>();
        }
        path.push(step);
        while (predecessors.get(step) != null) {
            step = predecessors.get(step);
            path.push(step);
        }
        // Put it into the correct order
        return path;
    }

}
